#include "main/utils.h"
using namespace std;

int rob_helper1(const vector<int>& nums, int begin, int end) {
  int dp[2][2];
  dp[0][0] = 0;
  dp[1][0] = nums[begin];
  for (int i = begin + 1; i < end; ++i) {
    int j = i - begin;
    dp[0][j % 2] = max(dp[0][(j - 1) % 2], dp[1][(j - 1) % 2]);
    dp[1][j % 2] = dp[0][(j - 1) % 2] + nums[i];
  }
  return max(dp[0][(end - begin - 1) % 2], dp[1][(end - begin - 1) % 2]);
}

int rob_helper2(const vector<int>& nums, int begin, int end) {
  vector<int> dp;
  dp.push_back(nums[begin]);
  dp.push_back(max(nums[begin], nums[begin + 1]));
  for (int i = begin + 2; i < end; ++i) {
    int j = i - begin;
    dp[j % 2] = max(dp[(j - 1) % 2], dp[(j - 2) % 2] + nums[i]);
  }
  return dp[(end - begin - 1) % 2];
}

int rob(const vector<int>& nums) {
  if (nums.size() == 0)
    return 0;
  if (nums.size() == 1)
    return nums[0];
  int rob1 = rob_helper2(nums, 0, nums.size() - 1);
  int rob2 = rob_helper2(nums, 1, nums.size());
  return max(rob1, rob2);
}

int main() {
  vector<int> nums = {2, 3, 4, 5, 3};
  cout << rob(nums) << endl;

  return 0;
}
